Search results for "Analysis of algorithm"
showing 10 items of 29 documents
A comprehensive probabilistic analysis of approximate SIR‐type epidemiological models via full randomized discrete‐time Markov chain formulation with…
2020
Spanish Ministerio de Economia y Competitividad, Grant/Award Number: MTM2017-89664-P; Generalitat Valenciana, Grant/Award Number: APOSTD/2019/128; Ministerio de Economia y Competitividad, Grant/Award Number: MTM2017-89664-P
A Probabilistic Analysis to Quantify the Effect of March 11, 2004, Attacks in Madrid on the March 14 Elections in Spain: A Dynamic Modelling Approach
2015
[EN] The bomb attacks in Madrid three days before the general elections of March 14, 2004, and their possible influence on the victory of PSOE (Spanish Workers Socialist Party), defeating PP (Popular Party), have been a matter of study from several points of view (i.e., sociological, political, or statistical). In this paper, we present a dynamic model based on a system of differential equations such that it, using data from Spanish CIS (National Center of Sociological Research), describes the evolution of voting intention of the Spanish people over time. Using this model, we conclude that the probability is very low that the PSOE would have won had the attack not happened.Moreover, after t…
Estimation of Granger causality through Artificial Neural Networks: applications to physiological systems and chaotic electronic oscillators
2021
One of the most challenging problems in the study of complex dynamical systems is to find the statistical interdependencies among the system components. Granger causality (GC) represents one of the most employed approaches, based on modeling the system dynamics with a linear vector autoregressive (VAR) model and on evaluating the information flow between two processes in terms of prediction error variances. In its most advanced setting, GC analysis is performed through a state-space (SS) representation of the VAR model that allows to compute both conditional and unconditional forms of GC by solving only one regression problem. While this problem is typically solved through Ordinary Least Sq…
A method for the probabilistic analysis of nonlinear systems
1995
Abstract The probabilistic description of the response of a nonlinear system driven by stochastic processes is usually treated by means of evaluation of statistical moments and cumulants of the response. A different kind of approach, by means of new quantities here called Taylor moments, is proposed. The latter are the coefficients of the Taylor expansion of the probability density function and the moments of the characteristic function too. Dual quantities with respect to the statistical cumulants, here called Taylor cumulants, are also introduced. Along with the basic scheme of the method some illustrative examples are analysed in detail. The examples show that the proposed method is an a…
Fast and Simple Approximation of the Diameter and Radius of a Graph
2006
The increasing amount of data to be processed by computers has led to the need for highly efficient algorithms for various computational problems. Moreover, the algorithms should be as simple as possible to be practically applicable. In this paper we propose a very simple approximation algorithm for finding the diameter and the radius of an undirected graph. The algorithm runs in $O(m\sqrt{n})$ time and gives an additive error of $O(\sqrt{n})$ for a graph with n vertices and m edges. Practical experiments show that the results of our algorithm are close to the optimum and compare favorably to the 2/3-approximation algorithm for the diameter problem by Aingworth et al [1].
Centering and Compound Conditionals under Coherence
2016
There is wide support in logic , philosophy , and psychology for the hypothesis that the probability of the indicative conditional of natural language, \(P(\textit{if } A \textit{ then } B)\), is the conditional probability of B given A, P(B|A). We identify a conditional which is such that \(P(\textit{if } A \textit{ then } B)= P(B|A)\) with de Finetti’s conditional event, B|A. An objection to making this identification in the past was that it appeared unclear how to form compounds and iterations of conditional events. In this paper, we illustrate how to overcome this objection with a probabilistic analysis, based on coherence, of these compounds and iterations. We interpret the compounds a…
A Probabilistic Approach to the Count-To-Infinity Problem in Distance-Vector Routing Algorithms
2013
Count-to-infinity problem is characteristic for routing algorithms based on the distributed implementation of the classical Bellman-Ford algorithm. In this paper a probabilistic solution to this problem is proposed. It is argued that by the use of a Bloom Filter added to the routing message the routing loops will with high probability not form. An experimental analysis of this solution for use in Wireless Sensor Networks in practice is also included.
On the Greedy Algorithm for the Shortest Common Superstring Problem with Reversals
2015
We study a variation of the classical Shortest Common Superstring (SCS) problem in which a shortest superstring of a finite set of strings $S$ is sought containing as a factor every string of $S$ or its reversal. We call this problem Shortest Common Superstring with Reversals (SCS-R). This problem has been introduced by Jiang et al., who designed a greedy-like algorithm with length approximation ratio $4$. In this paper, we show that a natural adaptation of the classical greedy algorithm for SCS has (optimal) compression ratio $\frac12$, i.e., the sum of the overlaps in the output string is at least half the sum of the overlaps in an optimal solution. We also provide a linear-time implement…
Quasi conjunction, quasi disjunction, t-norms and t-conorms: Probabilistic aspects
2013
We make a probabilistic analysis related to some inference rules which play an important role in nonmonotonic reasoning. In a coherence-based setting, we study the extensions of a probability assessment defined on $n$ conditional events to their quasi conjunction, and by exploiting duality, to their quasi disjunction. The lower and upper bounds coincide with some well known t-norms and t-conorms: minimum, product, Lukasiewicz, and Hamacher t-norms and their dual t-conorms. On this basis we obtain Quasi And and Quasi Or rules. These are rules for which any finite family of conditional events p-entails the associated quasi conjunction and quasi disjunction. We examine some cases of logical de…